#! /usr/bin/env python3
# coding = utf-8

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if target < candidates[0]:
            return []
        candidates.sort()
        can_map = dict([(candidates[i], i) for i in range(len(candidates))])
        stack = []
        c = candidates[:]
        res = []
        t = target
        while True:
            if c[0] <= t <= c[-1]:
                if t in can_map:
                    stack.append(t)
                    res.append(stack[:])
                    t = 0
            if t > c[-1]:
                t -= c[-1]
                stack.append(c[-1])
                continue

            while len(stack) > 0:
                tmp = stack.pop()
                t += tmp
                index = can_map[tmp]
                c = candidates[:index]
                if len(c) > 0:
                    break

            if len(stack) == 0 and len(c) == 0:
                    return res

s = Solution()
print(s.combinationSum([7, 3, 2], 18))